#include "main.h"
#include <cmath>

int g_currRound;
int g_bitsPerRound;

inline int keyIsBits(int num)
{
	int n = num >> g_currRound;
	int mask = ~(0xffffffff << g_bitsPerRound);
	n = n & mask;
	return n;
}

inline void exchange(int& a, int& b)
{
	int t = a;
	a = b;
	b = t;
}

// put negtive number to the left and positive number to the right
int preSort(int* array, int len)
{
	int i = -1, j = 0;
	for (; j < len; ++j)
	{
		if (array[j] < 0)
		{
			i++;
			exchange(array[i], array[j]);
		}
	}
	return i+1;
}

void _radixSort(int* array, int beg, int len)
{
	if (len <= 1) { return; }
	
	g_bitsPerRound = (int)(log(len) / log(2) + 0.5);
	g_currRound = 0;
	
	int roundCount = (int)ceil(32.0 / g_bitsPerRound); // int has 32 bits
	
	int max = ~(0xffffffff << g_bitsPerRound);
	
	for (g_currRound = 0; g_currRound < roundCount; ++g_currRound)
	{
		countingSort(array, len, max, beg, keyIsBits);
	}
}

void radixSort(int* array, int len)
{
	int pivotPos = preSort(array, len);
	_radixSort(array, 0, pivotPos);
	_radixSort(array, pivotPos, len-pivotPos);
}